package zcw.com.lib_leet_code;

import java.util.HashSet;
import java.util.Set;

/**
 * Created by 朱城委 on 2021/8/19.<br><br>
 *
 * 困难：缺失的第一个正数
 */
public class Topic41 {
    public static void main(String[] args) {
        Topic41 instance = new Topic41();

        int[] array = new int[] {1,2,0};
        System.out.println(instance.firstMissingPositive(array));

        array = new int[] {3,4,-1,1};
        System.out.println(instance.firstMissingPositive(array));

        array = new int[] {7,8,9,11,12};
        System.out.println(instance.firstMissingPositive(array));

        array = new int[] {1, 1};
        System.out.println(instance.firstMissingPositive(array));
    }

    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        int i = 0;
        for(; i < len; i++) {
            while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }

        i = 0;
        for(; i < len; i++) {
            if(nums[i] != i + 1) {
                return i + 1;
            }
        }

        return i + 1;
    }

    public int firstMissingPositive3(int[] nums) {
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] <= 0) {
                nums[i] = nums.length + 1;
            }
        }

        for(int i = 0; i < nums.length; i++) {
            int value = Math.abs(nums[i]);
            if(value <= nums.length) {
                nums[value - 1] = -Math.abs(nums[value - 1]);
            }
        }

        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) {
                return i + 1;
            }
        }

        return nums.length + 1;
    }

    public int firstMissingPositive2(int[] nums) {
        Set<Integer> set = new HashSet<>();

        for(int value : nums) {
            if(value > 0) {
                set.add(value);
            }
        }

        for(int i = 1; i < Integer.MAX_VALUE; i++) {
            if(!set.contains(i)) {
                return i;
            }
        }

        return Integer.MAX_VALUE;
    }
}
